Content addressable memory (CAM) devices are often used in applications which require high-speed database searching. For example, CAM devices are commonly used in network switches and routers to determine forwarding destinations and routing policies for incoming packets. In a typical application, a CAM device compares a selected portion of an incoming packet, referred to as a search key, with a database of values stored in an associative storage array within the CAM device. If the search key matches a stored value, the CAM device generates an index that corresponds to the location of the matching value within the storage array, and asserts a match flag to signal the match. The index is then typically used to address another storage array, either within or separate from the CAM device, to retrieve a destination address or other routing information for the packet.
FIG. 1 illustrates a prior-art CAM device, including a CAM array 101, comparand generator 103, priority encoder 105 and flag circuit 107. Search keys are input one after another to the comparand generator which responds by generating corresponding compare values (i.e., “comparands”) and differentially driving the compare values into the CAM array via compare signal lines 111. The CAM array 101 is an associative storage that includes an array of store-and-compare elements 109 referred to as CAM cells. Each CAM cell 109 includes a storage element to store a bit of data and a compare circuit to compare the bit of data to a comparand bit received via the compare signal lines 111. Because a dedicated compare circuit is provided within each CAM cells, database values stored in respective rows of the CAM cells may be simultaneously compared with a comparand value driven onto the compare signal lines 111. The compare circuits within each row of CAM cells are coupled in parallel to a respective match line 113. The match line is typically pulled up to a match-indicating level and pulled down to indicate a mismatch by any one or more of the match circuits that detect a mismatch between a stored value and an incoming comparand bit. The priority encoder and flag circuit are coupled to the match lines to receive the match signals (i.e., match line levels) from each row of CAM cells. The priority encoder generates a match index that corresponds to the address of the highest priority row of CAM cells for which a match is signaled, and the flag circuit generates a match flag signal that indicates, for each compare operation, whether a match was detected.
Over successive generations, CAM arrays have become increasingly dense, in some cases having several thousand CAM cells coupled to each compare signal line. As each CAM cell contributes a parasitic capacitance to the compare signal line, the capacitive loading in such large CAM arrays significantly increases the time required for a comparand bit to become valid (i.e., settle) along the length of a given compare signal line, thereby increasing the overall search cycle time and reducing the throughput of the CAM device.
One approach to reducing the capacitive loading in a large CAM array is to divide the CAM array into smaller, discrete arrays commonly referred to as CAM blocks, with each CAM block having a dedicated comparand generator, priority encoder and flag circuit. While such smaller arrays usually enable faster searching, replication of the comparand generator (and other circuitry, such as read/write circuitry) consumes significant die space within the CAM device, reducing the die space available for data storage.